In a modern communication system, signals may be transmitted from a source location to a destination location in analog or digital forms. Digital data communication has become more and more popular due to its various advantages in various applications. For example, it may offer increased capacity of data transmission, increased flexibility of data manipulation, etc. A signal that contains data derived from an image, a speech, etc., are typically encoded into sequences of symbols or binary symbols, which are then transmitted from a transmitter to a receiver through a data communication channel, e.g., via a cable or over-the-air. When transmitted through the communication channel, signals may be susceptible to interferences or noises, which may cause errors in the information on the receiver.
Certain techniques were developed to reduce data transmission errors in communication or to improve reliability of data communication. One example uses turbo codes, which may offer the performance approaching the Shannon limit, a theoretical limit for the maximum data transmission rate when data is transmitted over a noisy channel.
FIG. 1 illustrates a conventional non-binary (i.e., symbol-level) turbo code encoder 10 known in the prior art. Encoder 10 may include a grouping circuit 20, a permutation block 30, a modification block 40, a first non-binary convolutional code encoder 50 (C1), and a second non-binary convolutional code encoder 60 (C2). In FIG. 1, permutation block 30 and modification block 40 form a symbol-level interleaver, which processes input sequence u0 by symbols.
For example, an input sequence u0 having n binary bits may be grouped into N=n/W symbols (n and W both being positive integers, and typically n>W, and n being dividable by W) by the grouping circuit 20. Each symbol may include W binary bits from the input sequence u0. The grouped input sequence u0 may be directed through various circuits for processing. For example, the input sequence u0 may be directly output as an output sequence Y0 (Y0=u0) without any treatment. The input sequence u0 may also be directed to the first non-binary convolutional code encoder 50 (C1), where the input sequence u0 may be transformed and output as an output sequence Y1, which may have m bits (m may be a different integer from n, e.g., m>n). The input sequence u0 may further be directed to the permutation block 30 and the modification block 40 before being directed to the second non-binary convolutional code encoder 60 (C2). The second non-binary convolutional code encoder 60 (C2) may transform the sequence u2 and output the transformed sequence as an output sequence Y2, which may have m bits.
In the permutation block 30, the n/W symbols of the input sequence u0 may be permuted, the details of which will be discussed below. After permutation, the input sequence u0 may become a permuted sequence u1. Symbols in the permuted sequence us may be selectively modified by the modification block 40 according to a predetermined rule, which will be discussed in detail below. After the modification process, the sequence u1 may become a modified sequence u2. Finally, the modified sequence u2 may be directed into the second non-binary convolutional code encoders 60 (C2) for further processing.
A sequence u0 of n binary bits may be transformed into a sequence of m binary bits after being processed by the first and second encoders 50 (C1) and 60 (C2), where m>n, and the ratio of n/m is known as “code rate.” The first and second non-binary convolutional code encoders 50 (C1) and 60 (C2) may be structurally identical to each other, or different from each other. The first and second non-binary convolutional code encoders 50 (C1) and 60 (C2) may be implemented with different algorithms. For example, in some applications, the first non-binary convolutional code encoder 50 (C1) may output an output sequence Y1 with m1 bits (not shown in FIG. 1) and the second non-binary convolutional code encoder 60 (C2) may output an output sequence Y2 with m2 bits, where m1 may be different from m2. Therefore, in some embodiments, the first and second non-binary convolutional code encoders 50 (C1) and 60 (C2) may have different code rates. Since the first and second non-binary convolutional code encoders 50 (C1) and 60 (C2) are well known in the art, their details are not discussed herein.
FIG. 2 shows a diagram illustrating a non-binary turbo code encoder 70 with W=2 for a non-binary (symbol-level) turbo code defined in standards such as IEEE 802.16, DVB-RCS/RCT, etc. The input of the non-binary turbo code encoder 70 is a non-binary symbol, denoted as Sm, which may include a pair of data (A, B), where A and B are data units. An interleaver 80 of the non-binary turbo code encoder 70 may be a symbol-level interleaver, which may include the permutation block 30 and the modification block 40 shown in FIG. 1. The interleaver 80 may perform intra-symbol permutations or inter-symbol permutations. An intra-symbol permutation refers to a permutation within a symbol. For example, the data pair (A, B) may be permutated via an intra-symbol permutation to become another data pair (B, A). An inter-symbol permutation means a permutation between symbols. For example, a sequence containing a plurality of symbols [Sm,0, Sm,1, . . . , Sm,N−1] may be permutated to become another sequence containing the same symbols but arranged in a different order, e.g., [Sm,0, Sm,4, Sm,8, . . . , Sm,k], where k is a number from 0, 1, 2, . . . , N−1, and is determined based on a predetermined rule or algorithm.
Table 1 shows a conventional non-binary MAP algorithm known in the art, which may be implemented in the symbol-level interleaver 80. The algorithm includes two steps. Step 1 performs the intra-symbol permutation, for example, via the permutation block 30, and Step 2 performs the inter-symbol permutation using “Almost Regular Permutation (ARP),” for example, via the modification block 40. Before Step 1, a first sequence u0 may have already been grouped by the grouping circuit 20 shown in FIG. 1 into u0=[(A0, B0), (A1, B1), (A2, B2), (A3, B3), . . . , (AN−1, BN−1)], where data pair (Ai, Bi) includes a first data unit Ai and a second data unit Bi. In Step 1, each data pair (Ai, Bi) in the first sequence u0 is permuted between the first and second data units Ai and Bi, i.e., (Ai, Bi)→(Bi, Ai), if the condition (i mod 2=1) is satisfied, i=0, 1, 2, . . . , N−1. After permutation, a second sequence u1 may be generated from the first sequence u0. In Step 2, inter-symbol permutation is conducted. The jth data pair of a third interleaved sequence u2 is formed by the P(j)th data pair, which may be (Aj, Bj) or (Bj, Aj), of the second sequence u1, where P(j) is a mapping function providing a corresponding coordinate (i.e., address) of the jth data pair of the third sequence u2 in the second sequence u1. For an IEEE 802.16 symbol-level interleaver, the parameters P0, P1, P2, P3 used in the mapping function P(j) are constants known in the art, which are shown in Table 2.
TABLE 1IEEE 802.16 Symbol-Level Interleaver (Prior Art)Step 1: Switch alternate data pairs  Let the sequence u0 = [(A0,B0), (A1,B1), (A2,B2), (A3,B3), ..., (AN−1,BN−1)] be the input to  first encoder C1.  for i=0, 1,..., N−1  if ( (i mod 2) = 1), let (Ai,Bi)→ (Bi,Ai) (i.e., switch the data pair)  This step gives a sequence u1=[(A0,B0),(B1,A1),(A2,B2),...,(BN−1,AN−1)]=[u1(0),u1(1),u1(2),  u1(3), ...,u1(N−1)].Step 2: P(j)  The function P(j) provides the coordinate (i.e., address) of the data pair of the sequence  u1 that is mapped onto the coordinate (i.e., address) jth data pair of an interleaved  sequence u2 (i.e., u2(j) = u1(P(j))).  for j=0, 1,..., N−1  switch (j mod 4) :  case 0: P (j)= (P0j +1) mod N  case 1: P (j)= (P0j +1+N/2+P1) mod N  case 2: P (j)= (P0j +1+P2) mod N  case 3: P (j)= (P0j +1+N/2+P3) mod N  This step gives sequence u2=[u1(P(0)),u1(P(1)),u1(P(2)),u1(P(3)),...,u1(P(N−1))]=  [(BP(0),AP(0)), (AP(1),BP(1)),(BP(2),AP(2)),(AP(3),BP(3)),...,(AP(N−1),BP(N−1))]. Sequence u2 is the  input to second encoder C2.
TABLE 2Parameters for IEEE 802.16 Convolutional TurboCode Interleaver (Prior Art)InterleaverLength (Bytes)P0P1P2P3650009111801812132402418116062474824722711545623013600603617747224511900904811964814454131080108601312060180120536212224043643008243604372036054048031824166005366242
In a symbol-level interleaver design, the algorithm shown in Table 1 may require extra memory space for storing extrinsic information and a priori information generated during data processing in the decoder. As a result, the symbol-level interleaver 80 leads to higher complexity in decoder and may result in performance degradation in some applications in terms of higher error rates.
The disclosed embodiments may be directed to provide improvement(s) or alternative(s) to existing technology in certain data communication applications.